package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/5 10:15
 */
public class LC435无重叠区间 {

    public static int eraseOverlapIntervals(int[][] intervals) {
        return greedy(intervals);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(eraseOverlapIntervals(intervals));
    }

    private static int greedy(final int[][] intervals) {
        int answer = 0;
        Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[i - 1][1]) continue;           //没有重叠区间
            intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
            answer++;
        }
        return answer;
    }
}
